package leetcode.linkedlist;

/**
 * 61. 旋转链表
 *
 *
 */
public class RotateRight {

    public static void main(String[] args) {
        RotateRight solution = new RotateRight();

        Integer[] arr1 = {1,2,3,4,5};
        ListNode head = ListNode.makeLinkedList(arr1);

        ListNode newList = solution.rotateRight(head, 10);
        System.out.println(newList.list());
    }

    /**
     * 自己写的 超出时间限制
     *
     * @param head 链表
     * @param k    移动位数
     * @return
     */
    public ListNode rotateRight0(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head;
        while (k > 0) {
            newHead = rightMove(newHead);
            k--;
        }
        return newHead;
    }

    /**
     * 将链表每个节点向右移动 1 个位置
     *
     * @param head  链表
     * @return
     */
    public ListNode rightMove(ListNode head) {
        ListNode one = head;
        while (one.next.next != null) {
            one = one.next;
        }
        ListNode two = one.next;
        two.next = head;
        one.next = null;
        return two;
    }


    /**
     * 先闭环, 再找个指定的位置断开
     *
     * @param head  链表
     * @param k     移动步数
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }

        // 成环
        ListNode cur = head;
        // 链表长度
        int len = 1;
        while (cur.next != null) {
            cur = cur.next;
            len++;
        }
        cur.next = head;

        // 此时cur在最后一个节点
        int step = len - k%len;
        while (step > 0) {
            cur = cur.next;
            step--;
        }
        // 断开位置的下一个节点
        ListNode newHead = cur.next;
        // 环断开
        cur.next = null;
        return newHead;
    }
}
